/*
 * @lc app=leetcode.cn id=121 lang=swift
 *
 * [121] 买卖股票的最佳时机
 */

// @lc code=start
class Solution121 {
    // 买卖股票的最佳时机
    // 因为只能买卖一次，所以找到最小值，用后面的减去最小值形成的最大利润为最大利润
    func maxProfit(_ prices: [Int]) -> Int {
        var result = 0
        var minPrice = Int.max
        for item in prices {
            minPrice = min(item, minPrice)
            result = max(item - minPrice, result)
        }
        return result
    }
    // 动态规划，维持持有股票，不持有股票的状态
    // dp[i][1]表示"第i天持有股票所得最多现金"
    // dp[i][0] 不持有股票
    // dp[i][1] 持有股票
    func maxProfit2(_ prices: [Int]) -> Int {
        guard prices.count > 0 else {
            return 0
        }
        var dp = Array(repeating: Array(repeating: 0, count: 2), count: prices.count)
        // 第一天，不买，收益为0；第一天，买，收益为-prices[i]
        dp[0][0] = 0
        dp[0][1] = -prices[0]
        
        for i in 1..<prices.count {
            // 不持有：
            // 昨天不持有，保持不变
            // 昨天持有, 当今天卖出剩下现金 dp[i - 1][1] + prices[i]
            dp[i][0] = max(dp[i - 1][0],dp[i - 1][1] + prices[i])
            dp[i][1] = max(-prices[i], dp[i - 1][1])
        }
        
        return dp[prices.count - 1][0]
    }
    static func test() {
        let array = [7,1,5,3,6,4]
        let result = Solution121().maxProfit2(array)
        print(result)
    }
}
// @lc code=end

